package gold.digger;

import gold.utils.InputUtil;

import java.util.Arrays;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1220 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        int factor = 1000000007;

        public int countVowelPermutation(int n) {
            if (1 == n) return 5;
            long a = 1, e = 1, i = 1, o = 1, u = 1;
            long a1 = 1, e1 = 1, i1 = 1, o1 = 1, u1 = 1;
            for (int j = 0; j < n - 1; j++) {
                a = (e1 + i1 + u1) % factor;
                e = (a1 + i1) % factor;
                i = (e1 + o1) % factor;
                o = i1 % factor;
                u = (i1 + o1) % factor;

                // update
                a1 = a;
                e1 = e;
                i1 = i;
                o1 = o;
                u1 = u;
            }

            return (int) ((a1 + e1 + i1 + o1 + u1) % factor);
        }
    }

    class Solution_ACO {
        int MOD = (int) 1e9 + 7;

        public int countVowelPermutation(int n) {
            long[][] f = new long[n][5];
            Arrays.fill(f[0], 1);
            for (int i = 0; i < n - 1; i++) {
                // 每个元音 'a' 后面都只能跟着 'e'
                f[i + 1][1] += f[i][0];
                // 每个元音 'e' 后面只能跟着 'a' 或者是 'i'
                f[i + 1][0] += f[i][1];
                f[i + 1][2] += f[i][1];
                // 每个元音 'i' 后面 不能 再跟着另一个 'i'
                f[i + 1][0] += f[i][2];
                f[i + 1][1] += f[i][2];
                f[i + 1][3] += f[i][2];
                f[i + 1][4] += f[i][2];
                // 每个元音 'o' 后面只能跟着 'i' 或者是 'u'
                f[i + 1][2] += f[i][3];
                f[i + 1][4] += f[i][3];
                // 每个元音 'u' 后面只能跟着 'a'
                f[i + 1][0] += f[i][4];
                for (int j = 0; j < 5; j++) f[i + 1][j] %= MOD;
            }
            long ans = 0;
            for (int i = 0; i < 5; i++) ans += f[n - 1][i];
            return (int) (ans % MOD);
        }
    }


    public void run() {
        Solution solution = new Solution();

        Solution_ACO solution_aco = new Solution_ACO();

//        System.out.println(solution.countVowelPermutation(1));
//        System.out.println(solution.countVowelPermutation(2));
        for (int i = 2; i < 20; i++) {
            System.out.println(solution.countVowelPermutation(i) + " : " + solution_aco.countVowelPermutation(i));
        }

    }

    public static void main(String[] args) throws Exception {
        LC1220 an = new LC1220();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
